package com.shm.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeSet;

/**
 * 5497. 查找大小为 M 的最新分组  显示英文描述
 * 题目难度 Medium
 * 给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。
 *
 * 在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。
 *
 * 给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。
 *
 * 返回存在长度 恰好 为 m 的 一组 1  的最后步骤。如果不存在这样的步骤，请返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：arr = [3,5,1,2,4], m = 1
 * 输出：4
 * 解释：
 * 步骤 1："00100"，由 1 构成的组：["1"]
 * 步骤 2："00101"，由 1 构成的组：["1", "1"]
 * 步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
 * 步骤 4："11101"，由 1 构成的组：["111", "1"]
 * 步骤 5："11111"，由 1 构成的组：["11111"]
 * 存在长度为 1 的一组 1 的最后步骤是步骤 4 。
 * 示例 2：
 *
 * 输入：arr = [3,1,5,4,2], m = 2
 * 输出：-1
 * 解释：
 * 步骤 1："00100"，由 1 构成的组：["1"]
 * 步骤 2："10100"，由 1 构成的组：["1", "1"]
 * 步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
 * 步骤 4："10111"，由 1 构成的组：["1", "111"]
 * 步骤 5："11111"，由 1 构成的组：["11111"]
 * 不管是哪一步骤都无法形成长度为 2 的一组 1 。
 * 示例 3：
 *
 * 输入：arr = [1], m = 1
 * 输出：1
 * 示例 4：
 *
 * 输入：arr = [2,1], m = 2
 * 输出：2
 *
 *
 * 提示：
 *
 * n == arr.length
 * 1 <= n <= 10^5
 * 1 <= arr[i] <= n
 * arr 中的所有整数 互不相同
 * 1 <= m <= arr.length
 * @author SHM
 */
public class FindLatestStep {
    public int findLatestStep(int[] arr, int m) {
        int length = arr.length;
        List<Integer> list = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for (int i=0;i<length;i++){
            list.add(arr[i]);
            if (i>=m-1) {
                Collections.sort(list);
                for (int j=0;j<list.size()-1;j++){
                    int k = 1;
                    if (list.get(j+1)-list.get(j)==1){
                        k+=1;
                    }
                    if (k==m){
                        list2.add(i);
                    }
                }
            }
        }
        if (list2.size()==0) {
            return -1;
        }else{
            return list2.get(list2.size()-1);
        }
    }

    /**
     * 这题如果使用正向遍历，就需要考虑数组融合,这样会很麻烦，它既然求得是一个长度为 m 的一组 1 的最后步骤，其实等价于逆序出现第一个长度为 m 的一组 1 得步骤，例11101变为11111，题目找的是11101这个步骤，不就相当于找11111变为11101吗。
     *
     * 那么这题可以这么来做，逆序遍历，每次遍历可以看作将那个位置得1变为0（因为最终状态为全1，所以反向相当于1变为0）。这里我们以找到一个长度为2的一组 1为例，当前为110111,我们已经在下标为2的地方将1变为了0，如果接下来下标为5的地方将1变为了0，即变为110110,这时则存在长度为2的一组 1，即为所求。
     *
     * 算法流程：
     *
     * 添加边界 0，n+1；
     * 逆序遍历数组，查找当前值左右两边第一个已经被遍历到的数（相当于上例中，值5找值2，因为他们都已经被遍历了，对应下标的地方为0），如果存在长度为m的地方，return true；不然，将值存放在set中
     * 重复步骤2
     *
     * 作者：wwssxxu
     * 链接：https://leetcode-cn.com/problems/find-latest-group-of-size-m/solution/fan-xiang-qjing-wei-shen-sui-ran-wo-yun-xing-shi-j/
     * @param arr
     * @param m
     * @return
     */
    public int findLatestStep_2(int[] arr, int m) {
        TreeSet<Integer> set=new TreeSet<>();
        set.add(0);
        set.add(arr.length+1);
        if(arr.length==m){
            return arr.length;
        }
        int n=arr.length;
        for (int i = n-1; i >=0; i--) {
            int index=arr[i];
            //higher(E e) : 返回严格大于给定元素的该集合中的最小元素,没有返回null
            //lower(E e) : 返回这个集合中最大的元素严格小于给定的元素，如果没有这样的元素，则返回 null 。
            int a=set.lower(index);
            int b=set.higher(index);
            if(index-a-1==m||b-index-1==m){
                return i;
            }
            set.add(index);
        }
        return -1;
    }
}
